Many electronic devices have non-volatile memory connected to a processor to store data. The way data can be stored varies for different non-volatile memories. For instance, EEPROM memories typically allow byte wise programming. A single byte can be erased and reprogrammed. FLASH memories typically allow sector wise programming. In that case, a sector with a minimum sector size (typically 4 kB) must be erased before any single byte can be programmed in the sector. One can not erase and/or modify a previously written single byte in the sector within such (FLASH) memory. In order to modify a single byte, i.e. changing at least one bit from said signal byte from a logical ‘0’ to a logical ‘1’, the entire sector must be read from the (FLASH) memory and stored in a local, other memory (usually RAM) first. After that, the sector is erased in the FLASH memory. The byte that needs to be written is modified in the locally stored sector in the other memory and the entire sector in the FLASH memory is reprogrammed, i.e., the modified sector is transferred from the local other memory to the FLASH memory. So, in a FLASH memory one can only write a single byte to a memory location which has first been erased, and the act of erasing is performed sector wise. In other words, during an erase operation, all bits of a sector of a sector-wise erasable memory are set in an erased state, and during a storing operation one or more bits could only be changed from the erased state to programmed state.
In telephone applications the EEPROM memory is typically used for device settings, telephone books, menu settings and so on. When a user changes a setting, a corresponding data value is stored within a memory structure in for example a byte of the EEPROM, such that said byte contains that setting. The amount of times a byte can be reprogrammed without exceeding the loss of data retention guarantee is typically around 1 Million times for an EEPROM.
As an example, assume the volume setting of a headset in a busy call center is changed 10 times a day, 7 days a week, during the course of 10 years. This means the setting is changed 36.500 times, which is well within the EEPROM specification.
Now suppose the same information is stored in one or more bytes within a FLASH memory. Since a whole sector of the FLASH memory must be read, modified (in an other memory), erased and reprogrammed, this means that this sector is erased 36.500 times due to the desire to store this (these) byte(s) of information only. Suppose the surrounding bytes of that byte in the same sector have a 100 times lower refresh rate (volume setting changes a lot compared to other settings), then still the sector will be reprogrammed a total times of:36.500(due to volume setting)+(4096−1)*36.500/100[due to lower refresh rate of other bytes in the sector]=1.531.175 times
Given the fact that a typical sector in a FLASH memory may be erased about 10.000-100.000 times, it is clear that the “byte wise write” functionality of EEPROM memory can not be implemented in FLASH memory in a straightforward way.
In the prior art, several algorithms have been developed to emulate an EEPROM memory functionality into a FLASH memory. The goal of this emulation is to realize a cost saving by integrating the EEPROM memory functionality into the FLASH memory. In this way there is no need for a FLASH memory and an EEPROM memory together, but the system can suffice with just a FLASH memory. Even if a FLASH memory has more memory locations than an EEPROM memory it is considerably cheaper.
As an example, as shown in FIG. 1, assume an EEPROM memory 4 and a FLASH memory 3. The EEPROM memory 4 is 4 kB large in size. Typical prior art emulation systems allocate a larger memory space in FLASH memory 3, for instance 64 kB to emulate the 4 kB EEPROM memory 4 as is depicted in FIG. 1. The EEPROM memory 4 is divided into eight blocks 1 of 512 bytes. Each block 1 is represented by two sectors 2 and 5 in the FLASH memory 3. The sector 2 is active and the sector 5 is inactive. When the active sector 2 is full, the data in active sector 2 must be read out and stored in another, inactive sector 5 in order to prepare for erasing said active sector 2 later. Sector 5 operates as a backup memory for the data stored in active sector 2. In this way the reading, erasing, modifying and writing procedure can be restarted even if the system power is lost during the sequence and the locally, elsewhere stored contents of active sector 2 is lost since the backup data as stored in sector 5 can be used for that purpose.
As will be explained in detail below, more memory space is allocated in the FLASH memory 3 to store a certain amount of data, i.e., effectively every byte to be stored has multiple bytes allocated to it in the FLASH memory 3.
Prior art algorithms typically use the mechanism depicted in FIG. 2 to write data 14 to an allocated memory space 16 in the FLASH memory 3. If the software running on the processor requests the FLASH memory 3 to perform a byte write to a certain address in the emulated EEPROM, the prior art algorithms place a container 15 in the corresponding allocated sector in the FLASH memory 3. A container is a continuous part of memory space with a predetermined length in a sector. The container 15 consists of an address portion 13 and data portion 14. The data portion contains the data to be written to the FLASH memory 3. These containers 15 can be placed in any free container 12 in memory space 16. When the free container 12 is written, it is marked as a full container 11.
It is observed that writing data to a free container 12 in FLASH memory sector 16 can be done without having to erase the whole sector, as the empty container 12 has not been previously written. At the beginning of writing data in this sector the whole sector is erased, i.e., all bits are made logical “1”. After erasing a sector, all bits within a sector are in an erased state. This allows for a byte wise writing of all available erased bytes once within the FLASH memory directly without the need for such an erasing action. The bits that are changed from a logical “1” to a logical “0” due to the byte wise writing are in a programmed state.
When one of the active FLASH memory sectors is full, the processor will start a defragmentation process which may comprise the following actions:                The processor starts a sector reading action in which it reads all containers 15 as stored in the whole sector one-by-one in reverse order, i.e., the last stored container 15 is read first,        For every container 15, the processor checks the value of the address portion 13,        The processor checks whether it has read the value of the address portion in this sector reading action before,                    If yes, it ignores the presently read container 15 [because the content of the present container 15 relates to old, invalid data] and continues reading a next container 15,            If no, it stores the presently read container 15 in a local memory (e.g. RAM) and continues reading a next container 15,                        After finishing reading the whole sector in this way, the processor stores all containers 15 stored in local memory in a new sector in FLASH memory 3, which new sector has been erased before,        The processor erases the (old) sector.        
If the new sector is full the processor repeats the above actions but then the functions of the old and new sector are reversed. So, after defragmenting the content of the new sector, and storing defragmented data in local memory, the defragmented data is transferred from local memory to the old sector. Since the allocated sector in FLASH memory is large enough for storing data for a predetermined number of addresses this process can continue without the FLASH memory getting completely full.
In the prior art embodiment of FIG. 2, the address portion 13 of the container 12 has a one-to-one relation with one item, e.g., the volume setting of one headset of a set of headsets. Every time a new volume setting of the headset needs to be stored this is stored in the data byte 14 of a (new) container 15 in which the address byte 13 equals the address associated with the volume setting of this specific headset. Consequently, the FLASH memory 3 may comprise a plurality of containers 15 having the same address byte 13. The latest stored container 15 with this address, then, has the most recently stored volume setting. So, if the processor has to find the latest stored volume setting it has to look for the latest stored container 15 with this address.
One easy way to store new containers 15 would be to store every new container 15 in a consecutive next free part of the FLASH memory space 16. This may be called a “stack organization”.
The prior art method of retrieving a container 15 is illustrated in FIG. 3. To find a container 15 with a specific value in address 13 the containers as stored in FLASH memory 3 are read out in reverse order shown by arrow 17. Every dot 18 in the arrow 17 depicts a read action. Once the system has found the first container 15 with the specific address 13 value in a memory location, indicated with reference number 19 in FIG. 3, it has automatically found the latest data as the latest container will have been stored last in the FLASH memory space 16. Note that on average the system will read out half of the FLASH memory space 16 to find a container 15.
As an example, assume every container 15 consists of a 2 bytes address portion 13 and a 1 byte data portion 14. This means the total length of the container 15 is 3 bytes, so there are (4 kB/sector)/(3 B/container)=1365 containers/sector. So there are 1365 containers 15 available in the sector 16. As depicted in FIG. 1, 512 bytes of block 1 are mapped onto one active sector 2. So there are 1365 containers available for 512 bytes=2.66 containers/byte. As every container 15 can be written once, this means every byte of data can be stored 2.66 times on average in FLASH memory 3 before the 4 kB sector 16 is full.
Recalling the example of the headset application in a busy call centre, if, during the EEPROM lifetime, every byte is on average rewritten 36.500 times, then, on average, each FLASH memory sector 16 will be erased 36.500×/2.66=˜13.750 times. This is within specification for certain FLASH memories.
In order to retrieve a byte, the prior art algorithm must read out the entire sector 16 of the FLASH memory 3 until the last written data with a matching address is found. Assuming the data has been uniformly randomly written to FLASH memory 3 this means that on average a ½ sector must be read before the correct byte is allocated.